#include "sqstack.h"	//顺序栈基本运算及实现

//----递归算法------------------------------------------
void Hanoi1(int n, char a, char b, char c)
{
	if (n == 1)
		printf("\t将第%d个盘片从%c移动到%c\n", n, a, c);
	else
	{
        //请在下面编写代码
        /*************************Begin*********************/
        //将塔柱a上面的n-1个盘子移动到塔柱b，借助于塔柱c作为中转
		Hanoi1(n-1,a,c,b);
        /**************************End**********************/
		printf("\t将第%d个盘片从%c移动到%c\n", n, a, c);
		Hanoi1(n - 1, b, a, c);
	}
}

//----非递归算法------------------------------------------
void Hanoi2(int n, char x, char y, char z)
{
	StackType *st;							//定义顺序栈指针
	ElemType e, e1, e2, e3;
	if (n <= 0) return;						//参数错误时直接返回
	InitStack(st);							//初始化栈
	e.n = n; e.x = x; e.y = y; e.z = z; e.flag = false;
    //请在下面编写代码
    /*************************Begin*********************/
    //元素e进栈
    Push(st,e); 
    /**************************End**********************/

	while (!StackEmpty(st))					//栈不空循环
	{
        //请在下面编写代码
        /*************************Begin*********************/
        //出栈元素e
        Pop(st,e);
        /**************************End**********************/			
		if (e.flag == false)				//当不能直接移动盘片时
		{
			e1.n = e.n - 1; e1.x = e.y; e1.y = e.x; e1.z = e.z;
			if (e1.n == 1)					//只有一个盘片时可直接移动
				e1.flag = true;
			else							//有一个以上盘片时不能直接移动
				e1.flag = false;
			Push(st, e1);					//处理Hanoi(n-1,y,x,z)步骤
			e2.n = e.n; e2.x = e.x; e2.y = e.y; e2.z = e.z; e2.flag = true;

            //请在下面编写代码
            /*************************Begin*********************/
            //处理move(n,x,z)步骤
				Push(st,e2);
            /**************************End**********************/				
			e3.n = e.n - 1; e3.x = e.x; e3.y = e.z; e3.z = e.y;
			if (e3.n == 1)					//只有一个盘片时可直接移动
				e3.flag = true;
			else
				e3.flag = false;			//有一个以上盘片时不能直接移动
            
            //请在下面编写代码
            /*************************Begin*********************/
            //处理Hanoi(n-1,x,z,y)步骤
				Push(st,e3);
            /**************************End**********************/				
		}
		else								//当可以直接移动时
			printf("\t将第%d个盘片从%c移动到%c\n", e.n, e.x, e.z);
	}
	DestroyStack(st);						//销毁栈
}
 
